﻿package string;

/**
 * 给定一个字符串数组strs，再给定两个字符串str1,str2。返回在strs中str1和str2的最小距离
 * 
 * @author Administrator
 *
 */
public class 数组中两个字符串的最小距离 {
	/**
	 * 思路：用last1记录最近一次出现str1的位置，用last2记录最近一次str2出现的位置。
	 * 继续遍历，如果再发现str1,则i-last2，则最小距离是i-last,如果发现str2,则i-last1 是当前的最小距离.
	 * 
	 * @param str
	 * @param str1
	 * @param str2
	 * @return
	 */
	public static int minDistance(String[] str, String str1, String str2) {
		if (str1 == null || str2 == null)
			return -1;
		if (str1.equals(str2))
			return 0;

		int last1 = -1;
		int last2 = -1;
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < str.length; i++) {
			if (str[i].equals(str1)) {
				// 此时已经找到了str1
				min = Math.min(min, last2 == -1 ? min : i - last2);
				last1 = i;
			}
			if (str[i].equals(str2)) {
				// 此时已经找到了str2
				min = Math.min(min, last1 == -1 ? min : i - last1);
				last2 = i;
			}

		}
		return min == Integer.MAX_VALUE ? -1 : min;
	}

	public static void main(String[] args) {
		String[] str = { "1", "3", "3", "3", "3", "2", "3", "1", "11" };
		String str1 = "1";
		String str2 = "2";
		System.out.println(minDistance(str, str1, str2));
	}

	
}
